FIG. 1A is a diagram of a conventional wireless system 1. A transmitter 2 transmits packets to a radio 4 via a wireless channel 6.
There are inherent risks in transmitting data wirelessly. Bits in packets can be lost due to interference even in the best of configurations. One challenge for designers of wireless systems is how to recover packets with a few bad bits without having to re-transmit the entire packet. This problem is applicable to all communication applications in which a determination can be made whether a bit is valid or not.
A conventional solution to this problem is a radio 4 that determines which bits in a given received packet are valid, and an XOR (eXclusive OR) Checksum algorithm. The XOR checksum may then be used to correct invalid data bits. Commonly a byte at the end of packet is included that contains a ‘Column XOR Checksum’. The transmitter 2 computes this value by XORing all the same hits in each byte of the packet and putting the result as the last byte in the packet. After the packet has been transmitted, the receiver (radio) 4 checks for invalid bits. If an invalid bit is found, it can be corrected based on the Column XOR checksum.
FIG. 1 shows a conventional solution transmit side packet. The transmitted packet of this example has two bytes of data, and a checksum byte corresponding to the columns of data transmitted. FIG. 2 shows a conventional solution Receive side packet. This is the same packet that was transmitted in FIG. 1, but it has undergone processing on the receive side. The top row of FIG. 2 shows the bits corrected by the XOR error correction. The valid bit rows of FIG. 2 show where data bits may be suspect, due to corruption during transmission. There is a one to one correlation between the valid bits and the data bits.
FIG. 2 shows an example of packet received over the air by the radio with errors. Because Valid Byte 2, Bit 1 is 0 we know the radio could not determine whether Data Byte 2, bit 1 was a 1 or 0. By XORing the remaining bits (Data Byte 1, Bit 1; column XOR checksum, Bit 1) we can reconstruct the missing bit. Because there are two invalid bits in column 7 we are unable to correct this packet. The disadvantage of the conventional system is that it cannot correct for multiple bit erasures in the same column.
It would be desirable to have a solution that is more robust and can correct for multiple bit erasures in the same column.